package com.atguigu.algorithm;

import java.util.Deque;
import java.util.LinkedList;

public class MovingWindows {
    public static void main(String[] args) {
        int[] ret=maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
        for(int i:ret){
            System.out.print(i+" ");
        }
    }
    public static int[] maxSlidingWindow(int[] nums,int k){
        //k为滑动窗口的大小
        int[] res=new int[nums.length-k+1];
        Deque<Integer> deque=new LinkedList<>();
        int L=0;
        int R=0;
        while(R<k){
            if(deque.isEmpty()){
                deque.addLast(R++);
            }else{ //deque不为空，分两类情况
                while(nums[deque.peekLast()]<=nums[R]){
                    deque.pollLast();
                    if(deque.isEmpty()){
                        break;
                    }
                }
                deque.addLast(R++);
            }
        }
        res[0]=nums[deque.peekFirst()];
        //已经初始化成功了,开始R走一步，L走一步
        while(R<nums.length){
            //先进行R的
            if(deque.isEmpty()){
                deque.addLast(R++);
            }else{
                while(nums[deque.peekLast()]<=nums[R]){
                    deque.pollLast();
                    if(deque.isEmpty()){
                        break;
                    }
                }
                deque.addLast(R++);
            }
            //R已经走完了，L走
            if(L==deque.peekFirst()){
                deque.pollFirst();
                L++;
            }else{
                L++;
            }
            res[L]=nums[deque.peekFirst()];
        }
        return res;
    }
}
